/*
 * Copyright (c) 1997, 1998, 2003, 2006 Aleksandar Samardzic
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <assert.h>		/* for assert() function */
#include <stdlib.h>		/* for malloc() function */
#include "list.h"

/* List_Init - List class constructor */
void
List_Init(this)
     PList          *this;
{
	this->numItems = 0;
	this->pFirst = this->pLast = NULL;
}

/* List_Clean - List class destructor */
void
List_Clean(this)
     PList          *this;
{
	PListNode      *pCurr,
	               *pPrev;
	for (pCurr = this->pFirst; pCurr;) {
		pPrev = pCurr;
		pCurr = pCurr->pNext;
		free(pPrev);
	}
}

/* List_AddItem - add pointer to item to the end of list */
void
List_AddItem(this, pItem)
     PList          *this;
     void           *pItem;
{
	PListNode      *pNew;

	/* create new node */
	pNew = malloc(sizeof(PListNode));
	assert(pNew != NULL);
	pNew->pItem = pItem;
	pNew->pNext = NULL;

	if (this->pFirst)
		this->pLast = this->pLast->pNext = pNew;
	else			/* list was empty */
		this->pFirst = this->pLast = pNew;

	(this->numItems)++;
}

/* List_Empty - reset list */
void
List_Empty(this)
     PList          *this;
{
	PListNode      *pCurr,
	               *pPrev;
	for (pCurr = this->pFirst; pCurr;) {
		pPrev = pCurr;
		pCurr = pCurr->pNext;
		free(pPrev);
	}
	this->numItems = 0;
	this->pFirst = this->pLast = NULL;
}

/* List_Shuffle - random shuffle list items */
void
List_Shuffle(this, seed)
     PList          *this;
     int             seed;
{
	PListNode      *pListNode;
	int             numItems,
	                item;
	void          **ppItems,
	              **ppItem,
	              **ppItem0,
	              **ppItem1,
	              **ppItemTmp;

	/* initialize random number generator */
	srand(seed);

	/* allocate an array for list items */
	numItems = this->numItems;
	ppItems = malloc(numItems * sizeof(void *));
        assert(ppItems != NULL);

	/* copy list items into array */
	for (pListNode = this->pFirst, ppItem = ppItems; pListNode;
	     pListNode = pListNode->pNext, ppItem++)
		*ppItem = pListNode->pItem;

	/* shuffle array elements */
	for (item = 0; item < numItems; item++) {
		ppItem0 = ppItems + item;
		ppItem1 =
		    ppItems +
		    (int) (numItems * (rand() / (RAND_MAX + 1.0)));
		ppItemTmp = ppItem0;
		ppItem0 = ppItem1;
		ppItem1 = ppItemTmp;
	}

	/* insert items back to list */
	for (pListNode = this->pFirst, ppItem = ppItems; pListNode;
	     pListNode = pListNode->pNext, ppItem++)
		pListNode->pItem = *ppItem;
	free(ppItems);
}

/* ListIterator_Attach - attach list to iterator and initialize iterator */
void
ListIterator_Attach(this, pList)
     PListIterator  *this;
     PList          *pList;
{
	this->pList = pList;
	this->pCurr = pList->pFirst;
}

/* ListIterator_Next - return pointer to next item from list */
int
ListIterator_Next(this, ppItem)
     PListIterator  *this;
     void          **ppItem;
{
	if (!(this->pCurr))	/* end of iteration */
		return 0;

	*ppItem = this->pCurr->pItem;
	this->pCurr = this->pCurr->pNext;
	return 1;
}
